package kaiao.window;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author kai.ao
 * @since 2024/5/17
 */
public class 无重复字符的最长子串 {

	public static void main(String[] args) {
		int i = lengthOfLongestSubstring("abba");
	}

	public static int lengthOfLongestSubstring(String s) {

		// 设置Map记录包含元素 本质上是dic，记录元素位置
		Map<Character, Integer> dic = new HashMap<>();

		// 初始化左指针i的位置
		int i = -1, res = 0, len = s.length();
		for(int j = 0; j < len; j++) {

			// 如果map包含当前元素
			if (dic.containsKey(s.charAt(j))) {

				// 如果当前元素在i指针之前，则不需要更新i， 否则需要更新i 更新左指针 i（
				// i位窗口左边线值，如遇到包含的元素，需移动左边线值，将窗口范围缩小
				i = Math.max(i, dic.get(s.charAt(j)));
			}

			// 记录值与其指针位置
			dic.put(s.charAt(j), j);

			// 更新结果
			res = Math.max(res, j - i);
		}
		return res;
	}


	public int copyTest(String s) {
		Map<Character, Integer> dicMap = new HashMap<>();

		// 滑动窗口本质上是左右指针的运动，记录其某个时间点左右指针的最大值
		// 定义左指针
		int j = -1; int res = 0;

		// 右指针循环遍历
		for (int i = 0; i < s.length(); i++) {

			// 如果当前dic已包含当前元素，则说明左指针需要移动，通过max函数判断左指针是否需要移动，已在dic元素位置的后面则不需要移动
			if (dicMap.containsKey(s.charAt(i))) {

				j = Math.max(j, dicMap.get(s.charAt(i)));
			}

			dicMap.put(s.charAt(i), i);
			res = Math.max(res, i - j);
		}

		return res;
	}
}
